package com.datastructure.search.self;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class GoldenSearch {

    public static int maxSize = 20;

    public static void main(String[] args) {

    }

    public static int[] getFib(){
        int[] res = new int[maxSize];
        res[0] = 1;
        res[1] = 1;
        for(int i = 2;i<maxSize-1;i++){
            res[i] = res[i-1]+res[i-2];
        }
        return res;
    }

    public static List<Integer> getTargetList(int[] arr,int target){
        List<Integer> res = new ArrayList<>();
        int k = 0;
        int[] fib = getFib();
        while (arr.length-1>fib[k]) {
            k++;
        }
        int[] temp = Arrays.copyOf(arr,fib[k]);
        for (int i = arr.length; i < fib[k]-1; i++) {
            temp[i]=arr[arr.length-1];
        }
        int start = 0;
        int end = arr.length-1;
        while (start<end){
            int mid = start + temp[k-1]-1;
            if(target<temp[mid]){
                k--;
            }else if(target>temp[mid]){
                k-=2;
            } else {
                int buff = mid -1;
                while (true) {
                    if(buff<0||(temp[buff]!=temp[mid])){
                        break;
                    }
                    res.add(temp[buff]);
                    buff--;
                }
                res.add(temp[mid]);
                buff = mid + 1;
                while (true) {
                    if(buff> temp.length-1||(temp[buff]!=temp[mid])){
                        break;
                    }
                    res.add(temp[buff]);
                    buff++;
                }
            }
        }
        return res;
    }
}
